package 数据结构.树;

import java.util.ArrayList;
import java.util.LinkedList;
import java.util.Queue;

/**
 * @author Zhu
 * @Description
 * @create 2023-03-05
 */
public class JZ78把二叉树打印成多行 {
    ArrayList<ArrayList<Integer>> Print(TreeNode pRoot) {
        ArrayList<ArrayList<Integer>> list = new ArrayList<>();
        if(pRoot == null)
            return  list;
        Queue<TreeNode> q = new LinkedList<>();
        q.offer(pRoot);
        while (!q.isEmpty()){
            ArrayList<Integer> alist = new ArrayList<>();
            int n = q.size();
            for(int i=0;i<n;i++){
                TreeNode node = q.poll();
                alist.add(node.val);
                if(node.left!=null)
                    q.offer(node.left);
                if(node.right!=null)
                    q.offer(node.right);
            }
            list.add(alist);
        }
        return  list;
    }

    //递归层次遍历
        private void traverse(TreeNode root, ArrayList<ArrayList<Integer> > res, int depth) {
            if(root != null){
                //数组长度小于当前层数，新开一层
                if(res.size() < depth)
                    res.add(new ArrayList<Integer>());
                //数组从0开始计数因此减1，在节点当前层的数组中插入节点
                res.get(depth - 1).add(root.val);
                //递归左右时节点深度记得加1
                traverse(root.left, res, depth + 1);
                traverse(root.right, res, depth + 1);
            }
        }
        //层次遍历
        public ArrayList<ArrayList<Integer> > Print2(TreeNode pRoot) {
            ArrayList<ArrayList<Integer> > res = new ArrayList<ArrayList<Integer> >();
            //树的层级从1开始递归计数
            traverse(pRoot, res, 1);
            return res;
        }

}

